#pragma once
#include "..\AutoPtr\AutoPtr.h"
#include "..\Common\List.h"

template <typename _Type>
class Edge
{
public:
	int Number;
	int Position;
	_Type Weight;
	NAutoPtr<Edge> Next;
	Edge() : Number(-1),Position(-1){}
	Edge(int N,int P,_Type W) : Number(N),Position(P),Weight(W){}
};

template <typename _Type>
class Vertex
{
public:
	int Number;
	NAutoPtr<Vertex<_Type>> Next;
	NAutoPtr<Edge<_Type>> Out;

	Vertex() : Number(-1){}
	Vertex(int N) : Number(N){}
};

template <typename _Type>
class AdjancentTable
{
public:
	AdjancentTable() : numOfVertices(1),numOfEdges(0)
	{
		startVertex = new Vertex<_Type>(0);
	}

	int GetValueByPos(int Pos)
	{
		if((Pos >= 0) && (Pos < numOfVertices))
		{
			NAutoPtr<Vertex<_Type>> p = startVertex;
			for(int i=0;i<Pos;i++)
			{
				p = p->Next;
			}
			return p->Number;
		}
		return -1;
	}

	NAutoPtr<Edge<_Type>> GetOutByPos(int Pos)
	{
		if((Pos >= 0) && (Pos < numOfVertices))
		{
			NAutoPtr<Vertex<_Type>> p = startVertex;
			for(int i=0;i<Pos;i++)
			{
				p = p->Next;
			}
			return p->Out;
		}
		return new Edge<_Type>;
	}

	int GetPosByValue(int Value)
	{
		NAutoPtr<Vertex<_Type>> p = startVertex;
		for(int i=0;i<numOfVertices;i++)
		{
			if(p->Number == Value)
			{
				return i;
			}
			p = p->Next;
		}
		return -1;
	}

	_Type GetWeightByPos(int v1,int v2)
	{
		if((v1 >= 0) && (v2 >= 0) && (v1 < numOfVertices) && (v2 < numOfVertices))
		{
			NAutoPtr<Vertex<_Type>> p = startVertex;
			for(int i=0;i<v1;i++)
			{
				p = p->next;
			}
			NAutoPtr<Edge<_Type>> q = p->Out;
			while(q)
			{
				if (q->Position == v2)
				{
					return (q->Weight);
				}
				else
				{
					q = q->Next;
				}
			}
		}
		return new _Type;
	}

	_Type GetWeightByValue(int value1, int value2)
	{
		return GetWeightByPos(GetPosByValue(value1),GetPosByValue(value2));
	}

	void SetValue(int Value, int Pos)
	{
		if((Pos < 0) || (Pos >= numOfVertices))
		{
			return;
		}
		NAutoPtr<Vertex<_Type>> p = startVertex;
		for(int i=0;i<Pos;i++)
		{
			p = p->Next;
		}
		p->Number = Value;
	}

	void InsertVertex(int Value)
	{
		int pos = GetPosByValue(Value);
		if ((pos >= 0) && (pos < numOfVertices))
		{
			return;
		}
		NAutoPtr<Vertex<_Type>> p = startVertex;
		while(p->Next)
		{
			p = p->Next;
		}
		NAutoPtr<Vertex<_Type>> newVertex = new Vertex<_Type>(Value);
		p->Next = newVertex;
		numOfVertices++;
	}

	void InsertEdgeByPos(int v1,int v2,_Type Weight)
	{
		if ((v1 < 0) || (v1 >= numOfVertices) || (v2 < 0) || (v2 >= numOfVertices))
		{
			return;
		}
		NAutoPtr<Vertex<_Type>> p = startVertex;
		for(int i=0;i<v1; i++)
		{
			p = p->Next;
		}
		NAutoPtr<Edge<_Type>> q = p->Out;
		NAutoPtr<Edge<_Type>> newEdge = new Edge<_Type>(GetValueByPos(v2), v2, Weight);
		if(!q)
		{
			p->Out = newEdge;
			numOfEdges++;
			return;
		}
		while((q->Position != v2) && (q->Next))
		{
			q = q->Next;
		}
		if(q->Position == v2)
		{
			return;
		}
		if(!q->Next)
		{
			q->Next = newEdge;
			numOfEdges++;
		}
	}

	void InsertEdgeByValue(int value1,int value2,_Type Weight)
	{
		int v1 = GetPosByValue(value1), v2 = GetPosByValue(value2);
		InsertEdgeByPos(v1, v2, Weight);
	}

	void RemoveAllEdges()
	{
		NAutoPtr<Vertex<_Type>> p = startVertex;
		for(int i=0;i<numOfVertices;i++)
		{
			NAutoPtr<Edge<_Type>> q = p->Out;
			while(q)
			{
				p->Out = q->Next;
				//delete q;
				q = p->Out;
			}
			p = p->Next;
		}
		numOfEdges = 0;
	}

	void Clear()
	{
		RemoveAllEdges();
		NAutoPtr<Vertex<_Type>> p = startVertex->next;
		while(p)
		{
			startVertex->Next = p->Next;
			//delete p;
			p = startVertex->Next;
		}
		numOfVertices = 1;
	}

	int GetVerticeNum()
	{
		return numOfVertices;
	}

	int GetEdgeNum()
	{
		return numOfEdges;
	}

	int* Closure(int* L)
	{
		int i = 0, j, k = 0, l, len = 0;
		int* temp = new int[numOfVertices + 1];
		//for(int m=0;m<numOfVertices+1;m++)
		//	temp[m] = -1;
		NAutoPtr<Vertex<_Type>> p;
		NAutoPtr<Edge<_Type>> q;
		while(L[len] != -1)
			len++;
		while(L[i] != -1)
		{
			for(l=0;l<k;l++)
			{
				if(L[i] == temp[l])
				{
					break;
				}
			}
			if(l == k)
			{
				temp[k] = L[i];
				k++;
			}
			int pos = GetPosByValue(L[i]);
			p = startVertex;
			for(j=0;j<pos;j++)
			{
				p = p->Next;
			}
			q = p->Out;
			while(q)
			{
				if(q->Weight == new CharClass)
				{
					for (l=0;l<k;l++)
					{
						if (q->Number == temp[l])
						{
							break;
						}
					}
					if(l == k)
					{
						temp[k] = q->Number;
						k++;
						L[len++] = q->Number;
						L[len] = -1;
					}
				}
				q = q->Next;
			}
			i++;
		}
		temp[k] = -1;
		return temp;
	}

	int* Move(int *T,_Type ch)
	{
		int i = 0, j, k = 0, l;
		int *temp = new int[numOfVertices + 1];
		//for(int m=0;m<numOfVertices+1;m++)
		//	temp[m] = -1;
		NAutoPtr<Vertex<_Type>> p;
		NAutoPtr<Edge<_Type>> q;
		while(T[i] != -1)
		{
			int pos = GetPosByValue(T[i]);
			p = startVertex;
			for (j=0; j<pos; j++)
			{
				p = p->Next;
			}
			q = p->Out;
			while(q)
			{
				if (q->Weight == ch)
				{
					for (l=0; l<k; l++)
					{
						if (q->Number == temp[l])
						{
							break;
						}
					}
					if (l == k)
					{
						temp[k] = q->Number;
						k++;
					}
				}
				q = q->Next;
			}
			i++;
		}
		temp[k] = -1;
		return temp;
	}
protected:
	NAutoPtr<Vertex<_Type>> startVertex;
	int numOfVertices;
	int numOfEdges;
};